Random walks in small-world exponential treelike networks

摘要

In this paper, we investigate random walks in a family of small-world treeshaving an exponential degree distribution. First, we address a trappingproblem, that is, a particular case of random walks with an immobile traplocated at the initial node. We obtain the exact mean trapping time defined asthe average of first-passage time (FPT) from all nodes to the trap, whichscales linearly with the network order $N$ in large networks. Then, wedetermine analytically the mean sending time, which is the mean of the FPTsfrom the initial node to all other nodes, and show that it grows with $N$ inthe order of $N \ln N$. After that, we compute the precise global meanfirst-passage time among all pairs of nodes and find that it also varies in theorder of $N \ln N$ in the large limit of $N$. After obtaining the relevantquantities, we compare them with each other and related our results to theefficiency for information transmission by regarding the walker as aninformation messenger. Finally, we compare our results with those previouslyreported for other trees with different structural properties (e.g., degreedistribution), such as the standard fractal trees and the scale-freesmall-world trees, and show that the shortest path between a pair of nodes in atree is responsible for the scaling of FPT between the two nodes.